// 字符串匹配算法：暴力解法、RK 算法、BM 算法、KMP 算法
// 详细参见：算法基础课：应用篇 -> 字符串匹配
// 暴力
// 时间复杂度：O(m*n)
// 空间复杂度：O(1)
int strStr(char* haystack, char* needle) {
    int m = strlen(haystack);
    int n = strlen(needle);
    if (n > m) return -1;
    if (n == 0) return 0;
    char first = needle[0];
    int i;
    for (i = 0; i < strlen(haystack) - n + 1; i++) {
        // 如果等于 needle 的第一个字符，再进行 n 个字符的比较
        if (haystack[i] == first
                && (strncmp(haystack + i, needle, n) == 0)) {
            return i;
        }
    }
    return -1;
}

int* getNext(char* needle) {
    int n = strlen(needle);
    if (n == 1) return NULL;

    int* next = (int*)malloc(sizeof(int) * (n - 1));

    next[0] = -1;

    for (int j = 1; j < n - 1; j++) {
        int pre = next[j - 1];
        while (pre != -1 && needle[pre + 1] != needle[j]) {
            // 因为前一个最长串的下一个字符不与最后一个相等，所以需要找前一个的次长串
            // 问题就变成了求 0 到 next(pre) 的最长串
            pre = next[pre];
        }
        if (needle[pre + 1] == needle[j]) {
            pre++;
        }
        next[j] = pre;
    }
    // 最值问题
    return next;
}

// KMP
// 时间复杂度：O(m + n)
// 空间复杂度：O(n)
int strStr(char* haystack, char* needle) {
    int m = strlen(haystack);
    int n = strlen(needle);
    if (n == 0) return 0;
    if (m < n) return -1;

    int* next = getNext(needle);

    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j > 0 && haystack[i] != needle[j]) {
            j = next[j - 1] + 1;
        }

        if (haystack[i] == needle[j]) {
            j++;
        }

        if (j == n) {
            free(next);
            return i - n + 1;
        }
    }

    free(next);
    return -1;
}


